package org.huawei260.DP;

import java.util.Scanner;

/**
 * @Auther: qingle
 * @Date: 2024/8/19-14:05
 * @Description: 一天一只顽猴想要从山脚爬到山顶，
 * 途中经过一个有n个台阶的阶梯，
 * 但是这个猴子有个习惯，每一次只跳1步或3步
 * 试问？猴子通过这个阶梯有多少种不同的跳跃方式
 * @version: 1.0
 */
public class O0004_猴子爬山 {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
//			solution(n);
			solution2(n);
		}
	}

	// 给的答案看不懂
	private static void solution(int n) {
		int step1 = 1, step2 = 1, step3 = 2;
		int step4 = n == 1 || n == 2 ? 1 : 2;
		for (int i = 4; i <= n; i++) {
			step4 = step3 + step1;
			step1 = step2;
			step2 = step3;
			step3 = step4;
		}
		System.out.println(step4);
	}

	// 动态转移方程
	// 几种爬山方式 用dp存储起来，递推公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

	// dp[0] = 1;
	// dp[1] = 1;
	// dp[2] = 2;
	// dp[3] = 3;
	private static void solution2(int n) {
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 1;
		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 3];
		}
		System.out.println(dp[n]);
	}

}